package demo.src;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * 全局记录
 */
public class MazeGenerate {
    private volatile static MazeGenerate mazeGenerate;
    /** 预生成的路径 **/
    private List<int[]> root; //存放搜索的x,y坐标集
    /** 方向 **/
    private int[][] directions;
    /** 图 **/
    private char[][] maze;
    /** 已探索图 **/
    private boolean[][] seen;
    /** 八向索引 **/
    List<Integer> directionIdxs;
    private MazeGenerate (){
        //初始化化方向参数
        this.root=new ArrayList<int[]>();
        this.directions=new int[][]{
            {-1,-1},{-1,0},{-1,1},
            {0,-1},        {0,1},
            {1,-1}, {1,0}, {1,1}
        };
        this.directionIdxs=new ArrayList<Integer>();
        for(int i=0;i<8;i++){
            directionIdxs.add(i);
        }
    }

    /**
     * 单例模式
     * @return 方便调用本类
     */
    public static MazeGenerate getMazeGenerate() {
        if (mazeGenerate == null) {  
            synchronized (MazeGenerate.class) {
                if (mazeGenerate == null) {
                    mazeGenerate = new MazeGenerate();
                }
            } 
        } 
        return mazeGenerate;  
    }

    /**
     * 生成随机地图（由'■'和'*'构成）
     * <p> 生成随机路劲并添加
     * <p> 生成随机障碍物并添加
     * @param size 迷宫大小
     * @param barrierRate 障碍率
     * @param fast 策略
     * @return char[][]图
     */
    public char[][] generate(int size,double barrierRate,boolean fast){
        //初始化
        maze=new char[size][size];
        seen=new boolean[size][size];
        root=new ArrayList<int[]>();
        seen[0][0]=true;
        root.add(new int[]{0,0});
        //预设路径生成策略
        if(fast){
            fastPlan();
        }else{
            canFindRoot();
        }
        //预设路径root画到maze图中'*'
        for(int[] point:root){
            int x=point[0],y=point[1];
            maze[x][y]='*';
        }
        int barrierCount=(int) (size*size*barrierRate);        //障碍数
        //添加图对应的索引
        List<Integer> mazeIdxs=new ArrayList<Integer>();
        for(int i=0;i<size*size;i++){
            mazeIdxs.add(i);
        }
        //路径外添加障碍物'■'
        Collections.shuffle(mazeIdxs);//随机随机函数，打乱索引，产生随机性
        for(int mazeIdx:mazeIdxs){
            if(barrierCount==0){
                break;
            }
            int x=mazeIdx/size,y=mazeIdx%size;
            if(maze[x][y]!='*'){
                maze[x][y]='■';
                barrierCount--;
            }
        }
        //可移动位置赋值' '
        for(int x=0;x<size;x++){
            for(int y=0;y<size;y++){
                if(maze[x][y]!='■'){
                    maze[x][y]=' ';
                }
            }
        }
        return maze;
    }

    /**
     * 回溯算法生成root预设路径(待优化)
     * @return root
     */
    private boolean canFindRoot() {
        int[] point = root.get(root.size() - 1); // 取当前位置
        int x = point[0], y = point[1];

        // 如果已经访问过终点，则存在通路
        if (seen[maze.length - 1][maze[0].length - 1]) {
            return true;
        }

        Collections.shuffle(directionIdxs); // 随机打乱方向，用于随机遍历方位函数

        // 遍历方位函数
        for (int idx : directionIdxs) {
            // 生成新位置
            int[] direction = directions[idx];
            int nextX = x + direction[0];
            int nextY = y + direction[1];

            // 判断新位置是否合法，即在迷宫范围内且未被访问过
            if (nextX >= 0 && nextX < maze.length
                    && nextY >= 0 && nextY < maze[0].length
                    && !seen[nextX][nextY]) {
                root.add(new int[]{nextX, nextY}); // 将新位置添加至路径
                seen[nextX][nextY] = true; // 将新位置标记为已访问

                // 递归调用 canFindRoot()，继续探索新位置的通路
                if (canFindRoot()) {
                    return true; // 如果找到通路，返回true
                }

                root.remove(root.size() - 1); // 如果未找到通路，则从路径中移除新位置
                seen[nextX][nextY] = false; // 将新位置标记为未访问，以便其他路径继续尝试
            }
        }

        return false; // 当前位置及其所有扩展位置都无法找到通路，返回false
    }

    /**
     * 有目标的向前移动策略
     * <p> 向下或向有移动直到终点
     */
    private void fastPlan(){
        int x=0,y=0;
        // 将起始点加入 'root' 列表
        root.add(new int[]{x,y});
        // 循环直到当前位置 (x, y) 到达迷宫的右下角
        while(x!=maze.length-1||y!=maze[0].length-1){
            int xTemp=x,yTemp=y;
            //// 生成一个随机数 (0 或 1) 决定是水平方向还是垂直方向移动
            Random r=new Random();
            int target=r.nextInt(2);
            // 如果目标是 0 且我们没有到达迷宫的右边界，或者目标是 1 且我们到达了迷宫的右边界，则向右移动 (增加 x)
            if((target==0&&x<maze.length-1)||(target==1&&y==maze[0].length-1)){
                xTemp++;
            }else{
                // 否则向下移动 (增加 y)
                yTemp++;
            }
            // 如果下一个潜在位置 (xTemp, yTemp) 形成一条对角线，并且我们没有到达迷宫的右下角，则跳过当前循环
            if(xTemp==yTemp&&x!=maze.length-1&&y!=maze[0].length-1){
                continue;
            }
            // 将新位置加入 'root' 列表
            x=xTemp;
            y=yTemp;
            root.add(new int[]{x,y});
        }
    }

    /**
     * maze地图信息打印，用于测试
     */
    public void printMaze(){
        int size=maze.length;
        for(int x=0;x<size;x++){
            for(int y=0;y<size;y++){
                System.out.print(maze[x][y]);
            }
            System.out.println();
        }
    }

}
